1. Field
The following description relates to a heap sorting method based on arrangement and a data sorting method and apparatus thereof which improves heap sorting function by reducing I/O access of a memory.
2. Description of Related Art
Heap sort is a sorting method which uses a material structure called heap comprised of a binary tree, i.e., heap. It sorts data by comparing data of respective nodes. The heap sorting conducts data sorting by comparing the value of a parent node and a child node after comprising the maximum heap having the parent node value higher than that of the child node by determining the root node as a maximum value or after comprising minimum heap having the parent node value smaller than that of the childe node by determining the root value as the minimum value in converse.
FIG. 1 is a diagram schematically illustrating the access (I/O) between an external memory 110 and a main memory 120.
As illustrated in FIG. 1, the memory devices 110 and 120 has a basic access unit 140 according to shapes and they are operated in reference to the basic access unit 140 when the computer read and write data through accessing the memory devices 110 and 120.
When the size of the whole data which is the sorting subject during heap sorting is not big, the whole data can be transmitted to the main memory 120 of the computer through access (I/O, Input/Output) to the memory device 110. However, when the size of the whole data is big, the whole data cannot be transmitted to the main memory 120, thereby the data should be transmitted through accessing the external memory device 110 every time when conducting calculation for heap sorting.
Herein, the speed accessing the external memory device 110 is relatively slow thereby, the higher frequency of accessing the external memory, the slower the conducting speed of the heap sorting would be.
FIG. 2 is a diagram illustrating a data storing method of heap sorting according to a related art.
As illustrated in FIG. 2A, in the heap sorting according to a related art is stored in an order of second level from the root node 210 in reference to the basic access unit 140 of the memory 110.
As illustrated in FIG. 2B, when the size of the basic access unit 140 is 1024 KB, the heap sorting according to a related art is stored in the external memory device 110 to the level which satisfies 1024 KB from the root node 210 as the starting point. Further, the data from the second level to the level satisfying the 1024 KB is stored in the external memory device 110.
The heap sorting conducts sorting by comparing the parent node and the child node while, the heap sorting data storing method according to a related art stores the data of the parent node and child node in a different basic access unit 140 thus, the access (I/O) frequency in regards to the external memory device 110 increases. When the access (I/o) frequency in regards to the external memory device 110 increases, a lot of time is consumed in transmitting data thereby, there is a problem of slowing conducting speed of the whole heap sorting.
Especially, it can be a huge problem of data processing when the heap sorting conducting speed slows down in regards to a system of processing huge data like big data.